package 排序算法;

/**
 * 冒泡排序：
 * 从左到右取出每个数据与现有数据对比，大于就交换位置，小于就继续比较，直到所有数据扫描完成
 */
public class 冒泡排序 {

    public static void main(String[] args) {
        int[] arrays = {1, 56, 32, 56, 12, 77, 88, 21};
        for (int end = arrays.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                if (arrays[begin - 1] > arrays[begin]) {
                    int temp = arrays[begin - 1];
                    arrays[begin - 1] = arrays[begin];
                    arrays[begin] = temp;
                }
            }
        }

        //优化1 如果数组是有序的，提前推出循环
        for (int end = arrays.length - 1; end > 0; end--) {
            System.out.println("如果数组是有序的,只执行一次循环");
            boolean isSort = true;
            for (int begin = 1; begin <= end; begin++) {
                if (arrays[begin - 1] > arrays[begin]) {
                    int temp = arrays[begin - 1];
                    arrays[begin - 1] = arrays[begin];
                    arrays[begin] = temp;
                    isSort = false;
                }
            }

            if (isSort) break;
        }

        //优化2：记录交换的位置索引，提前推出循环。相比优化1，这种的几率会较大发生
        for (int end = arrays.length - 1; end > 0; end--) {
            int sortedIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (arrays[begin - 1] > arrays[begin]) {
                    int temp = arrays[begin - 1];
                    arrays[begin - 1] = arrays[begin];
                    arrays[begin] = temp;
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }

        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "_");
        }
    }


}
